package Year21_Month11.day1114;

public class Sort1 {
    public static void print(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
    //插入排序
    public static void insertSort(int[] arr){
        for(int i = 1;i < arr.length;i++){//注意从第二个元素开始
            int key = arr[i];
            int end = i - 1;//设置当前坐标
            //如果当前坐标小于key，那么当前坐标前移
            while(end >= 0 && arr[end] > key){
                if(arr[end] > key){
                    arr[end + 1] = arr[end];
                    end--;
                }
            }
            //最后这里的+1，是因为不论是否匹配成功end都要--
            arr[end + 1] = key;
        }
    }

    //希尔排序
    public static void shell(int[] arr){
        int size = arr.length;
        while(size > 1){
            //这里注意对每次的间隔进行变化
            size = size / 3 + 1;
            //每一个size对应一整次的遍历
            for(int i = size;i < arr.length;i++){
                int key = arr[i];
                int end = i - size;
                while(end >= 0 && arr[end] > key){
                    arr[end + size] = arr[end];
                    end -= size;
                }
                arr[end + size] = key;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {4,2,8,6,9,1,3,5,0,7};
        //insertSort(arr);
        shell(arr);
        print(arr);
    }
}
